package dualpointer;

public class D230830 {
    // 接雨水问题
    // 时间：O(N)
    // 空间：O(1)
    public long maxWater (int[] arr) {
        int res = 0;

        int n = arr.length;
        // 双指针遍历数组, 初始指向数组首尾
        int left = 0;
        int right = n - 1;

        // 记录左右边界的大小
        int maxL = 0;
        int maxR = 0;

        while (left < right) {
            // 先更新边界大小
            maxL = Math.max(maxL, arr[left]);
            maxR = Math.max(maxR, arr[right]);

            // 较矮的一边, 向中间移动
            // 并且根据 较矮的一边 确定水位
            if (maxL < maxR) {
                res += maxL - arr[left++];
            } else {
                res += maxR - arr[right--];
            }
        }
        return res;
    }
}
